import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-12-02
 * Time: 16:43
 */
public class test5 {
    /*
    LeetCode 95 不同的二叉搜索树II
    给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。
     */


    // 采用了分治的想法
    // 把整个数组分为了3个部分
    // 1.（start，i-1）
    // 2.（i）
    // 3.(i+1,end)


    public List<TreeNode> generateTrees(int n) {
        if(n==0){
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1,n);
    }

    public List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> mList = new LinkedList<TreeNode>();
        if(start>end){
            mList.add(null);
            return mList;
        }
        for(int i=start;i<=end;i++){
            List<TreeNode> leftTrees = generateTrees(start,i-1);
            List<TreeNode> rightTrees = generateTrees(i+1,end);
            for(TreeNode left:leftTrees){
                for(TreeNode right :rightTrees){
                    TreeNode curTree = new TreeNode(i);
                    curTree.left = left;
                    curTree.right = right;
                    mList.add(curTree);
                }
            }
        }
        return mList;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}
